package first_practice;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-560-和为k的子数组-代码注释已完成！
 * @date 2025/3/14 19:43
 */

//方法一：
//public class Solution560 {
//    public int subarraySum(int[] nums, int k) {
//        // 枚举和为k的子数组的右端点i，i从0一直到n-1
//        int n = nums.length;
//        int ans = 0;
//        for (int i = 0; i < n; i++) {
//            // 当确定了右端点i之后，从右往左枚举左端点j
//            int sum = 0;
//            for (int j = i; j >= 0; j--) {
//                sum += nums[j];
//                if (sum == k) ans++;
//            }
//        }
//        return ans;
//    }
//}

//方法二：
// 7 0 0  8  5       k = 15
// 7 7 7 15 20
//  只要有两个前缀和i,j的差等于k,且j<i,则代表出现了“和为k的子数组”
//  为什么要先加入map(0,1)呢？因为当第一次 pre[i] - k == 0 时,也就是 pre[i] == k
//  则代表一定有一个“和为k的子数组,为[0,1,2,...,i]”,这时候map中必须要有个1给它加进去
//  0代表了找到了“和为k的子数组”

public class Solution560 {
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        int pre = 0;
        Map<Integer, Integer> map = new HashMap<>(); // 存储每个前缀和出现的次数
        map.put(0, 1);
        for (int num : nums) {
            pre += num;
            ans += map.getOrDefault(pre - k, 0);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }
}